package algorithm.niuke;

public class 拼接最大数 {
    int index = 0;
    int[] res = null;
    int l1 = 0;
    int l2 = 0;
    int e1 = 0;
    int e2 = 0;

    public int[] maxNumber(int[] nums1, int[] nums2, int k) {
        if (index == 0) {
            l1 = nums1.length;
            l2 = nums2.length;
            res = new int[k];
            e1 = l1 - 1;
            e2 = l2 - 1;
        }
        find(nums1, 0, nums2, 0, k);
        return res;
    }

    void find(int[] nums1, int s1, int[] nums2, int s2, int k) {
        if (k == 0) {
            return;
        }
        int mMaxI = -1;
        for (int i = s1; i <= e1 && i < l1 + l2 - k + 1 + s1; i++) {
            if (mMaxI == -1) {
                mMaxI = i;
                continue;
            }
            if (nums1[i] > nums1[mMaxI]) {
                mMaxI = i;
            }
        }
        int nMaxI = -1;
        for (int i = s2; i <= e2 && i < l1 + l2 - k + 1 + s2; i++) {
            if (nMaxI == -1) {
                nMaxI = i;
                continue;
            }
            if (nums2[i] > nums2[nMaxI]) {
                nMaxI = i;
            }
        }
        boolean choose1 = nMaxI == -1;
        if (nMaxI != -1 && mMaxI != -1) {
            choose1 = nums1[mMaxI] > nums2[nMaxI];
        }

        if (choose1) {
            res[index++] = nums1[mMaxI];
            l1--;
            find(nums1, mMaxI + 1, nums2, s2, k - 1);
        } else {
            res[index++] = nums2[nMaxI];
            l2--;
            find(nums1, s1, nums2, nMaxI + 1, k - 1);
        }

    }

    public static void main(String[] args) {
        拼接最大数 run = new 拼接最大数();
        int[] nums1 = { 6, 7 };
        int[] nums2 = { 6, 0, 4 };
        int k = 5;
        run.maxNumber(nums1, nums2, k);
    }
}
